//  Representerer en tabellimplementasjon av en liste. Foran i listen er
//  ved indeks 0. Denne klassen vil bli utvidet ved arv for å gi en 
//  spesialisering. Vi sier at en klasse er avledet av en super-klasse.
///********************************************************************
 import java.util.Iterator;
 class TabellListe<T> implements ListeADT<T>{
   //Det som arves er det som er public eller protected.
   protected final int STD_KAPASITET = 100;
   protected final int IKKE_FUNNET = -1;
   protected int bak;
   protected T[] liste; 

   /******************************************************************
     Oppretter en tom liste med standard kapasitet.
   ******************************************************************/
   public TabellListe()
   {
      bak = 0;
      liste = (T[])(new Object[STD_KAPASITET]);
   }
   /******************************************************************
     Oppretter en tom liste med speisfisert kapasitet.
   ******************************************************************/
   public TabellListe (int startKapsitet){
      bak   = 0;
      liste = (T[])(new Object[startKapsitet]);
   }
   /******************************************************************
     Fjerner og returnerer det siste elementet i denne listen.
   ******************************************************************/
   public T fjernSiste (){
       T resultat = null;

      if (!erTom()){
         bak--;
         resultat = liste[bak];
         liste[bak] = null;
         }

      return resultat;
   }
   /******************************************************************
     Fjerner og returnerer det første elementet i denne listen.
   ******************************************************************/
   public T fjernFørste(){
   	
   	  T resultat = null;
   	  
      if (!erTom()){
          resultat = liste[0];
          bak--;
      /** skifert elementene en plass oppover */
      for (int i=0; i < bak; i++)
          liste[i] = liste[i+1];
 
      liste[bak] = null;
      }//if
 
      return resultat;
   }
   /******************************************************************
     Fjerner og returnerer det spesifiserte elementet.
   ******************************************************************/
   public T fjern (T element){
      T resultat = null;
     
      int indeks = finn(element);

      if (indeks != IKKE_FUNNET){
          
          resultat = liste[indeks];
          bak--;
          /** skifter elementene etter det vi fjernet en plass opp */
          for (int i=indeks; i < bak; i++)
                liste[i] = liste[i+1];
 
           liste[bak] = null;
      }//if

      return resultat;
   }
   
   /******************************************************************
     Returnerer en referanse til første elementet i denne listen.
     Elementet blir ikke fjernet.
     Hvis listen er tom returnerer null.  
   ******************************************************************/
   public T første() {
   	  T resultat = null;
      if (!erTom())
          resultat = liste[0];
      return resultat;    
   }

   /******************************************************************
     Returner en referanse til elementet bak i denne listen.
     Elementet blir ikke fjernet.
     Hvis listen er tom returneres null.   
   ******************************************************************/
   public T siste(){
   	  T resultat = null;
      if (!erTom())
      	resultat = liste[bak-1];
                  
      return resultat;
   }

   /******************************************************************
/Returnerer sann hvis denne listen inneholder det spesifiserte elementet.
   ******************************************************************/
   public boolean inneholder (T el) {
      return (finn(el) != IKKE_FUNNET);
   }


//     Returnerer tabellindeksen til det spesifiserte elementet.
//     Returnerer IKKE_FUNNET (-1) hvis ikke funnet.
//   ******************************************************************/
   protected int finn(T el){
      int i = 0, resultat = IKKE_FUNNET;
      boolean funnet = false;
      if (! erTom())
         while (! funnet && i < bak)

            if (el.equals(liste[i]))  //OBS: equals må implementeres i
                                      //     den klassen som bruker
               funnet = true;         //     metoden, for ellers blir
                                      //     det likhet på referanser.
            else                     
               i++;
      if (funnet)
         resultat = i;
      return resultat;
   }
   /******************************************************************
     Returnerer sann hvis denne listen er tom og usann ellers.. 
   ******************************************************************/
   public boolean erTom(){
      return (bak == 0);
   }
    /******************************************************************
     Returnerer antall elementer i denne listen.
   ******************************************************************/
   public int antall(){
      return bak;
   }
   /******************************************************************
     Returnerer en iterator for elementer i denne listen..
   ******************************************************************/
   public Iterator<T> iterator(){
      return new TabellIterator<T> (liste, bak);  // Eller ArrayIterator
   }
   /******************************************************************
     Returnerer en strengrepresentasjon av denne listen. 
   ******************************************************************/
   public String toString(){
      String resultat = "";

      for (int i=0; i < bak; i++) 
         resultat = resultat + liste[i].toString() + "\n";

      return resultat;
   }
   /******************************************************************
     Oppretter en ny og større tabell for må lagre innholdet av denne
     listen.
   ******************************************************************/
   protected void utvid()
   {
      T[] hjelpeTabell = (T[])(new Object[liste.length*2]);

      for (int i=0; i < liste.length; i++)
         hjelpeTabell[i] = liste[i];

      liste = hjelpeTabell;
   }
}//class